/*
 * @lc app=leetcode.cn id=321 lang=golang
 *
 * [321] 拼接最大数
 */

// @lc code=start
// package t

import "fmt"

// 本题使用单调栈获取每个数组最大的序列
// 然后对于每个数组最大的序列进行合并
func maxNumber(nums1 []int, nums2 []int, k int) []int {
	n1, _ := len(nums1), len(nums2)
	maxSeq := make([]int, k)
	for i := 0; i <= n1; i++ {
		seq1 := findMaxSeq(nums1, i)
		fmt.Println(i, k-1, seq1)
		if k-i < 0 {
			break
		}
		seq2 := findMaxSeq(nums2, k-i)
		// fmt.Println(seq1, seq2)
		seq := merge(seq1, seq2)
		if len(seq) < k {
			continue
		}
		if max(maxSeq, seq) {
			maxSeq = seq
		}
	}
	return maxSeq
}

// 比较序列大小
// 对于相同长度的数字序列，从左至右遍历，第一个不相同的数字谁大，则该数组大
func max(nums1, nums2 []int) bool {
	i := 0
	for ; i < len(nums1) && i < len(nums2); i++ {
		if nums1[i] != nums2[i] {
			return nums1[i] < nums2[i]
		}
	}
	if i < len(nums1) {
		return false
	} else {
		return true
	}

}

// 使用单调栈获取最大序列
// 但是本题的单调栈不同，它可能获取的单调栈无法达到长度k要求，因此我们只需要抛弃前面n-k个
// 后续不在抛弃
func findMaxSeq(nums []int, k int) []int {
	n := len(nums)
	d := n - k //需要删除的数量
	stack := make([]int, 0, k)
	for _, v := range nums {
		for len(stack) > 0 && d > 0 && v > stack[len(stack)-1] {
			stack = stack[:len(stack)-1]
			d--
		}
		if len(stack) < k {
			stack = append(stack, v)
		} else {
			d--
		}
	}
	if len(stack) > k {
		stack = stack[:k]
	}
	return stack
}

// 最大序列合并
// 当当前位置大小不一，取大
// 当大小想等时，比较后续大小，取后续大小大的
func merge(nums1, nums2 []int) []int {
	n1 := len(nums1)
	n2 := len(nums2)
	i, j := 0, 0
	tmp := make([]int, 0, n1+n2)
	for i < n1 && j < n2 {
		if nums1[i] > nums2[j] {
			tmp = append(tmp, nums1[i])
			i++
		} else if nums1[i] < nums2[j] {
			tmp = append(tmp, nums2[j])
			j++
		} else {
			if !max(nums1[i:], nums2[j:]) {
				tmp = append(tmp, nums1[i])
				i++
			} else {
				tmp = append(tmp, nums2[j])
				j++
			}
		}
	}
	if i < n1 {
		tmp = append(tmp, nums1[i:]...)
	}
	if j < n2 {
		tmp = append(tmp, nums2[j:]...)
	}
	return tmp
}

// @lc code=end
